package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * https://leetcode.cn/problems/count-complete-tree-nodes/description/
 * 二叉树的节点个数
 */
public class Code17_CountNode {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNodeUtils.getTreeNode();
        int count = countNodes(treeNode);
        System.out.println("full = " + count);

        int i = countNodes2(treeNode);
        System.out.println("i = " + i);
    }

    public static int countNodes(TreeNode treeNode) {
        return process(treeNode).nodes;
    }

    private static Info process(TreeNode treeNode) {
        if (treeNode == null) {
            return new Info(0, 0);
        }
        Info l = process(treeNode.left);
        Info r = process(treeNode.right);
        int h = Math.max(l.high, r.high) + 1;
        int nodes = l.nodes + r.nodes + 1;
        return new Info(h, nodes);
    }

    private static class Info {
        public int high;
        public int nodes;

        public Info(int high, int nodes) {
            this.high = high;
            this.nodes = nodes;
        }
    }

    public static int countNodes2(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        } else {
            return countNodes2(treeNode.left) + countNodes2(treeNode.right) + 1;
        }
    }
}
